package _15dijkasta;

import java.util.*;
import java.math.*;
import java.io.*;

public class dijksta2 {
	static int INF = 0x3f3f3f3f;
	static int N = 101000 , M = 2*N;
	static int n,m,k;
	static int[] h = new int[N],e = new int[M],ne = new int[M],w = new int[M];
	static int idx;
	static int[] dist = new int[N],st = new int[N];
	static void add(int a,int b,int c) {
		e[idx] = b;
		w[idx] = c;
		ne[idx] = h[a];
		h[a] = idx++;
	}
	static int dijkstra() {
		Arrays.fill(dist, INF);
		PriorityQueue<PII> q = new PriorityQueue<PII>((a,b)->(a.dist-b.dist));
		q.add(new PII(0,1));
		dist[1]=0;

		while(q.size()>0) {
			PII top = q.poll();
			
			if(st[top.ver]==1) continue;
			st[top.ver]=1;
			
			for(int i=h[top.ver];i!=-1;i=ne[i]) {
				int j = e[i];
				if(dist[j]>dist[top.ver]+w[i]) {
					dist[j] = dist[top.ver]+w[i];
					q.add(new PII(dist[j],j));
				}
			}
		}

		return dist[n];
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		Arrays.fill(h, -1);
		for(int i=1;i<=m;i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			
			add(a,b,c);

		}
		int ans = dijkstra();
		if(ans==INF) System.out.println(-1);
		else System.out.println(ans);
	}

	
}
class PII{
	int dist,ver;
	
	public PII(int dist,int ver) {
		// TODO Auto-generated constructor stub
		this.dist = dist;
		this.ver = ver;
	}
}
